This invention relates to a method of and system for providing publicly verifiable translation certificates that verify that an output encryption of a plaintcxt message corresponds to the input encryption of the same plaintext message. Translation certificates can be used in quorum controlled asymmetric proxy cryptography for encrypting and decrypting transcripts, with particular usefulness for Internet and E-mail applications.
With the increasing importance of encryption methods for privacy and protection of business secrets, and with an increasing need for a flexible infrastructure, I foresee the need for many new secure and flexible primitives extending the basic communication and encryption capabilities available today. One such primitive is proxy re-encryption, which Blaze et al. introduce in M. Blaze, G. Bleumer, M. Strauss, xe2x80x9cAtomic Proxy Cryptography,xe2x80x9d EUROCRYPT ""98, pp. 127-144. Proxy re-encryption is a translation between ciphertexts from one encryption key to another encryption key. It can be used to forward encrypted messages without having to expose the cleartexts to the participants involved, a primitive with many potential commercial uses.
In symmetric proxy encryption, which was exhibited by Blaze et al., the proxy (that is, the entity performing the translation) needs to know the secret keys associated with both the incoming and outgoing transcripts, or some linear combination of these. On the other hand, in asymmetric proxy re-encryption, it is not necessary for the proxy to know the secret key corresponding to the produced ciphertext. This is, therefore, a setting that is more realistic and practical than the symmetric setting.
The shortcomings of existing E-mail systems are well known, for example, in one existing E-mail system incoming E-mail messages are protected with a public key encryption and sent directly to the primary recipient""s mailbox. A problem with this scheme arises when the primary recipient leaves or is absent for an extended period of time and E-mails sent to the primary recipient are needed. In this instance, the contents of the E-mails can not be accessed by any other users, unless they have the absent primary recipient""s secret key. Thus, the information contained in these E-mails, regardless of how urgently it is needed or vitally important it is to an organization is inaccessible until the primary recipient returns or the primary recipient""s secret key is obtained.
Another existing E-mail system uses a single system administrator to distribute incoming E-mail messages to the intended primary recipients. This configuration can experience similar problems with those of the above described system if, for example, distribution of the E-mail is controlled by a single system administrator with the secret key and this system administrator leaves or is absent. In addition, in this system, the system administrator has total, unrestricted access to all E-mail messages in the system. While the problem of a missing system administrator can be overcome by having multiple E-mail system administrators (all of whom possess knowledge of the secret key), it multiplies the security problems by increasing the number of people who have unrestricted access to the E-mail system and, thus, makes confidential communications between parties less secure.
In another existing E-mail system, a group of system administrators are needed to distribute the E-mail. Incoming E-mail can be decrypted by the group of system administrators only if the entire group agrees and each uses their portion of the secret key to decrypt their associated portion of the E-mail message. Therefore, if an E-mail message in the primary recipient""s mailbox needs to be forwarded on, and the primary recipient is not available, all of the group of system administrators must decrypt their respective portions of the message, combine the results, and then forward the message to the necessary secondary recipients. A major problem with this system is that all of the system administrators must be available and once the decryption is finished, each system administrator in the group of system administrators has unrestricted access to the complete E-mail message.
Finally, in an existing symmetric proxy encryption system the proxy holds a key that allows the proxy to transform the transcripts, but which also allows the proxy to compute the secret key of the secondary recipient, given knowledge of the proxy""s own secret key. This, also, allows the secondary recipient to compute the secret key of the primary recipient or proxy server in a similar manner. This type of proxy encryption is disadvantageous in situations where there is no symmetric trust (or little trust at all). It also forces the participants to establish the shared transformation key ahead of time. The only advantage of a solution of this type appears to lie mainly in a potential improvement in efficiency, caused by the merging of the two decrypt and encrypt operations into one re-encryption operation performed during the transformation phase.
In my prior U.S. application Ser. No. 09/222,716, which is expressly incorporated by reference as to its entire content, I proposed a proxy encryption system which overcomes the disadvantages of the prior art systems. In this prior application I demonstrated how to implement quorum controlled asymmetric proxy re-encryption to guarantee that there is no dishonest quorum, that a plaintext message whose encryption is being transformed is not revealed to the proxy servers, and introduced the concept of verifying that the output encryption of a plaintext message corresponds to the input encryption of the same plaintext message.
All of the above techniques and systems fail to provide for the use of publicly verifiable translation certificates to verify the output encryption of a plaintext message corresponds to the input encryption of the same plaintext message without revealing the input encryption to either a subset of proxy servers or verifiers, in general, and the use of translation certificates in a quorum controlled asymmetric proxy re-encryption system, in particular. Therefore, there is a need for a system and new techniques to provide translation certificates for use in encrypting and decrypting transcripts.
My invention demonstrates how to use translation certificates to implement a quorum controlled asymmetric proxy re-encryption system to guarantee that there is no dishonest quorum and that the plaintext message whose encryption is being transformed is not revealed to the proxy servers.
My invention implements the use of publicly verifiable translation certificates in quorum controlled asymmetric proxy re-encryption systems. A proxy is an entity that is composed of one or more individuals called proxy servers. In my invention, a publicly verifiable translation certificate is generated by the xe2x80x9cproxy serversxe2x80x9d after they transform a transcript from being associated with a primary recipient to afterwards being associated with at least one secondary recipient. In one embodiment of the present invention, a quorum of proxy servers is selected from the available group of proxy servers to perform the transformation function and generate the translation certificate. The xe2x80x9cquorum of proxy serversxe2x80x9d can consist of any and all sufficiently large subsets of proxy servers from the group of proxy servers as described in detail in copending U.S. application Ser. No. 09/222,716. The exact membership of the quorum does not need to be identified until the time of the transformation, however, the minimum number of members in the quorum must be specified by the primary recipient before the secret key is shared among a quorum of the proxy servers. For example, in a group of five (5) proxy servers, if the primary recipient specified that a minimum of three (3) proxy servers would constitute a quorum, then the weighting necessary to decrypt the secret key would be dynamically determined so that any three of the currently available proxy servers would be able to decrypt the secret key, perform the necessary functions on the ciphertext, and generate the translation certificate. While, in the present invention, the proxy is intended to consist of more than one proxy server, the present invention is still applicable to a single proxy server.
I focus on asymmetric proxy re-encryption, where for security, the transformation and generation of the translation certificate is performed under quorum control by a quorum of proxy servers. This guarantees that if there is not a dishonest quorum, then a valid translation certificate is generated and the plaintext message whose encryption is being transformed is not revealed to the proxy servers. My solution is publicly verifiable, compact, and does not leak any information about the plaintext to any of the verifiers who verify the honesty of the participating proxy servers or to a subset of the proxy servers.
There are two types of asymmetric proxy transformations in which to implement translation certificates. In the first, which is merely theoretical, the message of the initial encryption can be hidden from the proxy by not requiring the proxy to know the decryption key corresponding to the proxy""s own public key (but where the proxy is still able to perform the transformation). In the second, in which the proxy is distributed and all actions are quorum controlled, the message of the encryption is hidden from a xe2x80x9csufficiently honestxe2x80x9d proxy. The second, in which the control is held by a quorum of proxy servers, has efficient solutions and I elaborate on such an embodiment herein.
A partial result of this proxy re-encryption system is the generation of a transcript from a non-interactive proof, that proves the correct translation between encryptions was performed, that is, that the incoming and outgoing encryptions indeed encrypt the same message. The transcript, which I call a translation certificate is publicly verifiable, is compact (using standard security parameters (|p|=1024 and |q|=160), it is a mere 396 bytes long and is generated independently of the number of provers), and does not leak any information about the plaintext to the verifiers or to a subset of the provers.
Consequently, my method and system for providing publicly verifiable translation certificates solves the above-mentioned deficiencies in the prior art system. My method and system involves receiving an input encryption having a first secret key; then outputting an output re-encryption of the input encryption, where the output re-encryption has a second secret key; and then generating a translation certificate that verifies that the input encryption and the output re-encryption are encryptions of an identical message, with respect to a first and a second public key.
Such a mechanism is useful in many applications. For example:
It allows the proxy to transform encrypted messages to encryptions with a variety of different recipient public keys, to allow for categorization of the encryptions. The categorization may be performed either as a function of the transcripts and their origins, randomly (for example, assigning an examiner to an electronically submitted patent), or as a function of time, and may be used to sort the encrypted messages according to priority or security clearance.
It allows more efficient communication to a large number of recipients that are physically clustered around the proxy; the sender would only need to send one encryption, along with an authenticated list of recipients. This may prove very useful for pay-tv, general multi-cast, and related applications.
It can be used for escrow encryption to separate the power of who can transform an encrypted message into a new transcript and who can read the plaintext message corresponding to such a transcript.
Lastly, I believe that asymmetric proxy encryption may become a useful building block in the design of secure and efficient multi-party protocols.